package com.leetcode.partition6;

/**
 * @author `RKC`
 * @date 2021/8/27 10:24
 */
@SuppressWarnings("DuplicateExpressions")
public class LC516最长回文子序列 {

    public static int longestPalindromeSubseq(String s) {
        return dynamicProgramming(s);
    }

    public static void main(String[] args) {
        String str = "bbbab";
        System.out.println(longestPalindromeSubseq(str));
    }

    private static int dynamicProgramming(String s) {
        //dp[i][j]表示字符串s[i, j]的最长回文子串
        int[][] dp = new int[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) dp[i][i] = 1;
        for (int length = 2; length <= s.length(); length++) {
            for (int i = 0; i + length - 1 < s.length(); i++) {
                int j = i + length - 1;
                if (length == 2) {
                    dp[i][j] = s.charAt(i) == s.charAt(j) ? 2 : 1;
                    continue;
                }
                //长度大于等于3
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 2 : 0));
            }
        }
        return dp[0][s.length() - 1];
    }

    private static int dynamicProgramming1(final char[] s) {
        //dp[i][j]：字符串s[i, j]范围内最长回文子序列的长度
        int[][] dp = new int[s.length][s.length];
        //任何长度为1的子序列都是回文子序列
        for (int i = 0; i < s.length; i++) dp[i][i] = 1;
        //但s[i]==s[j]时，dp[i][j]=dp[i+1][j-1]+2，因此需要考虑遍历顺序，i反序遍历，j正序遍历，但j>=i
        for (int i = s.length - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.length; j++) {
                dp[i][j] = s[i] == s[j] ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][s.length - 1];
    }
}
